package main

import (
	"fmt"
)

// numDistinct 动态规划解法
func numDistinct(s string, t string) int {
	var result int = 0
	tmp := make(map[int][]int)
	tmpn := make(map[int][]int)
	lt := len(t)

	if len(s) == lt {
		if s == t {
			return 1
		}
		return 0
	}

	if lt == 1 {
		for _, v := range s {
			v1 := fmt.Sprintf("%c", v)
			if v1 == t {
				result = result + 1
			}
		}
		return result
	}

	for i := 0; i < lt; i++ {
		tv := fmt.Sprintf("%c", t[i])
		for j := 0; j < len(s); j++ {
			sv := fmt.Sprintf("%c", s[j])
			if sv == tv {
				tmp[i] = append(tmp[i], j)
			}
		}
	}

	for k, v := range tmp {
		tmpn[k] = make([]int, len(v))
	}

	for i := 0; i < lt; i++ {
		if i == 0 {
			for j := 0; j < len(tmp[i]); j++ {
				tmpn[i][j] = 1
			}
			continue
		}

		for k, v := range tmp[i] {
			r := 0
			for kj, vj := range tmp[i-1] {
				if v > vj {
					r = r + tmpn[i-1][kj]
				}
			}
			tmpn[i][k] = r
		}
	}

	for i := 0; i < len(tmpn[lt-1]); i++ {
		result = result + tmpn[lt-1][i]
	}

	return result
	//fmt.Println(tmp)
	//return Recursive(tmp, -1, 0, len(t)-1)
}

func main() {
	//fmt.Print(numDistinct("babgbag", "bag"))
	fmt.Print(numDistinct("adbdadeecadeadeccaeaabdabdbcdabddddabcaaadbabaaedeeddeaeebcdeabcaaaeeaeeabcddcebddebeebedaecccbdcbcedbdaeaedcdebeecdaaedaacadbdccabddaddacdddc", "bcddceeeebecbc"))
}
